package uba.algo3.tp3.tsp;

import java.util.ArrayList;

public class Exacto
{
	private Grafo g;
	private Solucion sol;
	private int costoMin = Integer.MAX_VALUE;
	private int costoMin2 = Integer.MAX_VALUE;
	private ArrayList<Integer> solucion_parcial2;
	
	public Grafo getG()
	{
		return g;
	}

	public void setG(Grafo g)
	{
		this.g = g;
	}
	
	public Exacto(Grafo g)
	{
        this.g = g;
	}
	
	public Solucion get2TSP()
	{
		int n = g.getN();
		int i = 3;
		int tam_part1 = n + 1 - i, tam_part2 = 3;
		int costoMinTotal = Integer.MAX_VALUE;
		Solucion solFinal = null;
		
		while(tam_part1 >= tam_part2)
		{
			
			ArrayList<Integer> sol_parcial = new ArrayList<Integer>();
			sol_parcial.add(g.getOrig());
			
			Solucion s_part = solucion_particion(tam_part1, sol_parcial);
			int costoTotal = s_part.getCosto(); 
			
			if(costoTotal < costoMinTotal){
			
				solFinal = s_part;
				costoMinTotal = costoTotal;
				costoMin = costoTotal;
				System.out.println("costo minimo: " + costoMin);
				System.out.println("sol final: " + solFinal.getCiclo1() + " " + solFinal.getCiclo2() + " " + "costo: " + solFinal.getCosto());
			}
			
			i++;
			
			tam_part1 = n + 1 - i;
			tam_part2 = i;
		}
		
		return solFinal;
	}

	private Solucion solucion_particion(int tam_part1, ArrayList<Integer> solucion_parcial)
	{
		int n = g.getN();
		int nodo_orig = g.getOrig();
		
		if(solucion_parcial.size() == tam_part1)
		{
			ArrayList<Integer> solucion_nueva = new ArrayList<Integer>();
			ArrayList<Integer> complemento = g.getComplemento(solucion_parcial);
			int tam_part2 = complemento.size();
			solucion_nueva.add(nodo_orig);
			complemento.remove((Object) nodo_orig);
			mejorSolucion(tam_part2, complemento,solucion_nueva); 
			costoMin2 = Integer.MAX_VALUE;
			int costo = g.calcular_costo(solucion_parcial) + g.calcular_costo(solucion_parcial2);
			//System.out.println("Solucion hallada para: " + solucion_parcial + " " + solucion_parcial2 + " .Costo: " + costo);
			if(costo < costoMin)
			{
				sol = new Solucion(solucion_parcial,solucion_parcial2,costo);
				//NUEVA SOLUCION
				costoMin = costo;
			}
		}
		else
		{
			for(int i = 1; i <= n;i++)
			{
				if(i != nodo_orig && !solucion_parcial.contains(i))
				{
					solucion_parcial.add(i);
					solucion_particion(tam_part1, solucion_parcial);
					solucion_parcial.remove((Object) i);
				}
			}
		}
		
		return sol;
	}

	private ArrayList<Integer> mejorSolucion(int tam_part2, ArrayList<Integer> complemento, ArrayList<Integer> solparcial)
	{
		if(solparcial.size() == tam_part2)
		{
			int costo = g.calcular_costo(solparcial);
			
			if(costo < costoMin2)
			{
				costoMin2 = costo;
				solucion_parcial2 = (ArrayList<Integer>) solparcial.clone(); 
			}
		}
		else
		{
			for(int i = 0; i < complemento.size();i++)
			{
				int temp = complemento.get(i);
				solparcial.add(temp);
				complemento.remove(i);
				mejorSolucion(tam_part2, complemento,solparcial);
				complemento.add(i,temp);
				solparcial.remove((Object) temp);
			}
		}
		return solucion_parcial2;
	}
	
}
